Low-Density Parity Check (LDPC) Codes
Error correcting codes play a vital role in communication, computer, and storage systems by ensuring the integrity of data. The past decade has witnessed a surge in research in coding theory which resulted in the development of efficient coding schemes based on low-density parity check (LDPC) codes. Iterative message passing decoding algorithms together with suitably designed LDPC code ensembles have been shown to approach the information-theoretic channel capacity in the limit of infinite codeword length. LDPC codes are standardized in a number of applications such as wireless networks, satellite communications, deep-space communications, and power line communications.
For a (N, K) LDPC code with length N, dimension K, the parity check matrix (PCM) H of size M×N=(N−K)×N (assuming that H is full rank), is composed of a small number of ones. We denote the degree of the j-th column, i.e. the number of ones in the j-th column, by dv(j), 1≤j≤N. Similarly, we denote the degree of the i-th row, i.e. the number of ones in the i-th row, by dc(i), 1≤i≤M. Further, we define the maximum degree for the rows and columns:
                              γ          =                                    max                              1                ≤                j                ≤                N                                      ⁢                                          d                v                            ⁡                              (                j                )                                                    ⁢                                  ⁢                  ρ          =                                    max                              1                ≤                i                ≤                M                                      ⁢                                          d                c                            ⁡                              (                i                )                                                                        (        1        )            
When the number of ones in the columns and the rows of H is constant, the LDPC code is called regular, otherwise the LDPC code is said irregular. For regular LDPC codes, we have γ=dv=dv=dv(j), 1≤j≤N, and ρ=dc=dc(i), 1≤i≤M. The (dv, dc)-regular LDPC code ensemble represents a special interesting type of LDPC codes. For this type, the code rate is R=K/N=1−dv/dc if the PCM H is full rank.
If a binary column vector of length N, denoted x=[x1, x2, . . . , xN]T, is a codeword, then it satisfies Hx=0, where the operations of multiplication and addition are performed in the binary field GF(2), and 0 is the length-M all-zero column vector. xT denotes the transposition of x, both for vectors and matrices. An element in a matrix can be denoted indifferently by Hm,n or H(m, n). Similarly, an element in a vector is denoted by xn or x(n). The horizontal concatenation, respectively vertical concatenation, of vectors and matrices is denoted [A, B], respectively [A; B].
Quasi-Cyclic LDPC Codes The present invention particularity relates to the class of quasi-cyclic LDPC codes (QC-LDPC). In QC-LDPC codes, the PCM H is composed of square blocks or submatrices of size L×L, as described in Equation (2), in which each block Hi,j is either (i) a all-zero L×L block, or (ii) a circulant permutation matrices (CPM).
                    H        =                  [                                                                      H                                      1                    ,                    1                                                                                                H                                      1                    ,                    2                                                                              …                                                              H                                      1                    ,                                          N                      b                                                                                                                                            H                                      2                    ,                    1                                                                                                H                                      2                    ,                    2                                                                              …                                                              H                                      2                    ,                                          N                      b                                                                                                                          ⋮                                            ⋮                                            ⋮                                            ⋮                                                                                      H                                                            M                      b                                        ,                    1                                                                                                H                                                            M                      b                                        ,                    2                                                                              …                                                              H                                                            M                      b                                        ,                                          N                      b                                                                                                    ]                                    (        2        )            
A CPM is defined as the power of a primitive element of a cyclic group. The primitive element is defined, for example, by the L×L matrix, α, shown in Equation (3) for the case of L=8. As a result, a CPM αk, with k∈{0, . . . , L−1} has the form of the identity matrix, shifted k positions to the left. Said otherwise, the row-index of the nonzero value of the first column of αk, is k+1. The value of k is referred to as the CPM value. The main feature of a CPM is that it has only a single nonzero element in each row/column and can be defined by its first row/column together with a process to generate the remaining rows/columns. The simplicity of this process translates to a low hardware resources needed for realizing physical connections between subsets of codeword bits and parity check equations in an LDPC encoder or decoder.
                    α        =                  [                                                    0                                            0                                            0                                            0                                            0                                            0                                            0                                            1                                                                    1                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                                                    0                                            1                                            0                                            0                                            0                                            0                                            0                                            0                                                                    0                                            0                                            1                                            0                                            0                                            0                                            0                                            0                                                                    0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                                                    0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                                                    0                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                                                    0                                            0                                            0                                            0                                            0                                            0                                            1                                            0                                              ]                                    (        3        )            
The PCM of a QC-LDPC code can be conveniently represented by a base matrix (or protograph matrix) B, with Mb rows and Nb columns which contains integer values, indicating the powers of the primitive element for each block Hi,j. Consequently, the dimensions of the base matrix are related to the dimensions of the PCM the following way: M=Mb L, N=Nb L, and K=KbL (assuming that H is full rank). An example of matrices H and B for Mb×Nb=4×5 and L=8 is shown in Equation (4).
                              H          =                      [                                                                                α                    7                                                                                        α                    1                                                                                        α                    4                                                                                        α                    3                                                                    0                                                                                                  α                    2                                                                    0                                                                      α                    3                                                                    I                                                                      α                    4                                                                                                                    α                    4                                                                                        α                    6                                                                    0                                                  I                                                                      α                    2                                                                                                I                                                                      α                    2                                                                                        α                    7                                                                    0                                                                      α                    5                                                                        ]                          ⁢                                  ⁢                  B          =                      [                                                            7                                                  1                                                  4                                                  3                                                                      -                    ∞                                                                                                2                                                                      -                    ∞                                                                    3                                                  0                                                  4                                                                              4                                                  6                                                                      -                    ∞                                                                    0                                                  2                                                                              0                                                  2                                                  7                                                                      -                    ∞                                                                    5                                                      ]                                              (        4        )            
where I=α0 is the identity matrix, and by convention α−∞=0 is the all-zero L×L matrix.
General Circulant Matrices
In this invention, the blocks Hi,j are square L×L matrices, which are either a CPM or a all-zero block. However, the process of encoding a codeword x cannot be made from the PCM, but from a generator matrix G, as explained in paragraph 006. There are rare exceptions where the encoding can be performed directly with H, like in the case of low density generator matrices (LDGM) codes, but we do not discuss those cases in this disclosure.
General circulant matrices, not restricted to single CPMs, can appear during the process of computing G from H. A circulant matrix C is defined by the sum of w CPM with distinct powers:
                    C        =                              ∑                          k              =              1                        w                    ⁢                      α                          i              k                                                          (        5        )            where ik≠ik′, 0≤ik≤L−1 and 0≤ik′≤L−1, ∀(k, k′). In this definition, w is called the weight of circulant C, and we have 0≤w≤L. Special cases of circulants are: (i) when w=0, the circulant is the all-zero block, (ii) when w=1, the circulant is a CPM.
Encoding
This invention pertains to LDPC codes and their encoders and is applicable to any QC-LDPC code class, regular or irregular.
A codeword of an LDPC code, x=[x1, x2, . . . , xN]T, is created from a vector of information bits u=[u1, u2, . . . , uK]T, following the equation x=G u, where G is a generator matrix of the code. Without loss of generality, we assume that G is put in a systematic form, and that the codeword is organized as
                    x        =                  [                                                    u                                                                    r                                              ]                                    (        6        )            where r=[r1, r2, . . . , rM]T is the vector of redundancy bits.
In general, a generator matrix G can be obtained from a parity check matrix H by computing the reduced row echelon form of H, by means of Gaussian Elimination (GE). Since H is composed of circulants, and it is known that the inverse of a circulant matrix is also a circulant matrix, it follows that G is also composed of circulants, although not necessarily reduced to CPMs. The encoding equation becomes:
                    x        =                              [                                                            u                                                                              r                                                      ]                    =                                    Gu              ⇒              x                        =                                          [                                                                            u                                                                                                  r                                                                      ]                            =                                                [                                                                                    I                                                                                                            P                                                                              ]                                ⁢                                                                  ⁢                u                                                                        (        7        )            where P is a dense matrix composed of general circulants.
For QC-LDPC codes, the GE process can be performed at the circulant level, making use only of operations on circulant matrices (multiplications, additions, inverse). This also means that the leading coefficients used to pivot the matrix during GE are themselves circulant matrices. Two operations can increase the weights of the circulants:                When the leading coefficient is found, one needs to compute its inverse to create an identity block at the pivoting location on the main diagonal. If the leading coefficient is not a CPM, its inverse is usually a large weight circulant,        After the leading coefficient is turned into the identity, the corresponding block-row is combined with the other remaining block-rows in order to build the block-row echelon form. This combination of block-rows creates also large weight circulants.        
An alternative of using a direct inverse of matrix H is to transform it into an upper triangular matrix, using a greedy Sparse Gaussian Elimination. In GE, one can stop the process when the block-row echelon form has been found, that is when the resulting matrix is in upper triangular form. For a matrix which contains all-zeros blocks and a small number of CPM, the Gaussian Elimination algorithm can be constrainted such that the resulting upper triangular matrix is the sparsest possible. Indeed, if the reduced block-row echelon form is unique and corresponds to the inverse of the original matrix, its block-row echelon form is not unique and depends on the sequence of leading coefficients that are used to perform the Gaussian Elimination. In other words, depending on the sequence of leading coefficients, one can get different encoding matrices with different sparseness. The encoding equation become
                    Hx        =                  0          ⇒                      [                                                                                H                    1                                                                                                                                                                H                          2                                                ⁢                                                                                                  ]                                            ⁡                                              [                                                                                                            u                                                                                                                                          r                                                                                                      ]                                                              =                                                                  0                        ⇒                                                                                                            H                              1                                                        ⁢                            u                                                    +                                                                                    H                              2                                                        ⁢                            r                                                                                              =                      0                                                                                                                              (        8        )            where H1 is a dense matrix of size Mb×Kb composed of general circulants, and H2 is an upper triangular matrix (at the block level), of size Mb×Mb, also composed of general circulants. The encoder proceeds in two steps: (i) the first step consists in computing the parity check values of the first part of Equation (8), c=H1 u, (ii) the second step recursively computes the values of the redundancy bits r using backward propagation, since the matrix H2 is upper triangular.
To summarize, matrices P or (H1, H2) are used to perform the encoding, depending on the chosen encoding procedure. Those matrices are usually composed of general circulant blocks with large weights, typically of the order of L/2, where L is the circulant size. From the hardware complexity standpoint, it is advantageous to design design QC-LDPC codes for which the corresponding encoding matrix is as sparse as possible:                1. first, the number of operations involved in (7) and (8) grows linearly with the density of matrices P and (H1, H2). If those matrices have large weights, hardware implementations of (7) or (8) would suffer from either a large complexity, or a limited throughput. Having circulant blocks with large weights in the encoding matrices is not compliant with our objective of having an encoder with low complexity and high throughput.        2. matrices P and (H1, H2) may contain a combination of circulant blocks with large weight, and others with low weights (even some CPM). However, the circuits that implement sparse circulant multiplication or dense circulant multiplication are different. As a result, an encoder using (7) or (8) would need a special circuit for the sparse multiplication, and a another circuit for dense multiplication, which is not optimal in terms of hardware re-use and lead to unnecessary large complexity.        
It is therefore highly beneficial to consider an encoding procedure where the encoding matrices are sparse, composed of circulant blocks with low weights. The sparseness of the encoding matrix is not ensured by the classical encoding methods. We propose in this invention a method to use a very sparse representation of the encoding matrix, in order to obtain an encoding architecture which has both low complexity and high throughput.
Layers and Generalized Layers of QC-LDPC Codes
For a base matrix B of size (Mb, Nb), the rows (or block-rows of H) are referred to as horizontal layers (or row layers). The concept of layer has been introduced originally for the case of regular array based QC-LDPC codes, where the base matrix is full of CPMs, and contains no α−∞, i.e., no all-zero L×L block.
The concept of layers in a base matrix can be further extended to the concept of generalized layer (GL). The definition follows:                A generalized layer is defined as the concatenation of two or more layers of the base matrix, such that in each block-column of the generalized layer there is at most one CPM while its other elements are all-zero blocks.        A full generalized layer has further the property that each block-column contains exactly one CPM.        
This definition ensures that for a QC-LDPC code with maximum column degree γ, the PCM can be organized with at least γ GLs. For simplicity, we will assume that the number of GLs is always equal to the maximum column degree γ.
FIG. 1 shows an example of a PCM organized in γ=4 full GLs, indicated by 101, 102, 103 and 104. In this example, each of the GL contains 4 simple layers, for a total of Mb=16 block-rows in the base matrix. In general, each GL may contain a different number of block-rows, as long as the GL constraint in above definition is satisfied. In this example, the first GL 101 indicated in grey is composed of the first four block-rows of the base matrix.
In a PCM with a generalized layers structure, the block-rows of each generalized layer may be organized in an arbitrary order, and do not necessarily contain consecutive block-rows. In FIG. 2, we show an example of the matrix of FIG. 1, for which the block-rows of each GL have been regularly interleaved. Although the block-rows of the GL are not consecutive, this organization of a PCM still has the property that each GL contains a maximum of one non-zero block per column of the GL. For example the block rows 201, shown in grey, indicates the block-rows which compose GL1, which are deduced from GL1 in FIG. 1 by block-row interleaving.
The purpose of the GL organization of the PCM is to be able to perform processing of at least γ PCM blocks in parallel, without data access conflicts. This allows a larger degree of parallelism in the encoder/decoder algorithms, and leads to higher processing throughputs. Although the concept of layers and generalized layers for QC-LDPC codes has been introduced in the literature to improve the efficiency of the LDPC decoders, we show in this disclosure that such structure can also be beneficial for the QC-LDPC encoder.
QC-LDPC with Minimum Row-Gap Between Circulants
The organization of H in generalized layers is proposed to improve the throughput of the encoder. However, in order to reach very high throughputs, the PCM needs to have other constraints, with respect to the location of the CPM in each block-row. This constraint, that will be used in the description of this invention, is called gap constraint, and reflects the number of all-zero blocks that are between two consecutive CPM in the same block-row of H. On FIG. 1, we show an example of two consecutive circulants in the first block-row of H which are separated by three all-zero blocks. The gap between these two circulants is gap=4 blocks.
Let bi be the vector which stores the positions of nonzero blocks in the i-th row of the base matrix B. The vector bi is a length dc(i) vector, such that Bi,bi,k is a CPM and Bi,j with j≠bi,k is a all-zero block. Let us further denote the gap profile of row i by the vector gapi such thatgapi,k=bi,k+1−bi,k 1≤k≤dc(i)−1  (9)
For example, for the matrix in (4), we have b3=(1, 2, 4, 5), and gap3=(1, 2, 1).
For the whole QC-LDPC matrix, the minimum gap is defined as:
                              gap          *                =                              min                          1              ≤              i              ≤                              M                b                                              ⁢                      {                                          min                                  1                  ≤                  k                  ≤                                                                                    d                        c                                            ⁡                                              (                        i                        )                                                              -                    1                                                              ⁢                              {                                  gap                                      i                    ,                    k                                                  }                                      }                                              (        10        )            
Obviously, any QC-LDPC code has minimum gap*=1. As explained later in this disclosure, using QC-LDPC codes with a constraint on the minimum gap*>1 allows to derive encoders with larger throughputs. The gap constraint gap*>1 can be enforced by direct design of the PCM or the BM of the QC-LDPC code, or by re-arrangement of the columns.